Given a positive integer n, how many ways can we write it as a sum of consecutive positive integers?
Example 1:
Input: n = 5 Output: 2 Explanation: 5 = 5 = 2 + 3
Example 2:
Input: n = 9 Output: 3 Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4
Example 3:
Input: n = 15 Output: 4 Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
Note: 1 <= n <= 10 ^ 9.
Average Rating: 3.50 (62 votes)
Overview
Find Divisors / Integer Factorization Problem
N is a sum of k consecutive numbers, i.e. N=(x+1)+(x+2)+...+(x+k).
Let's regroup the terms N=xk+(1+2+...+k) and use well-known formula for the sum of natural numbers 1+2+...+k=2k(k+1):
N=xk+2k(k+1)(1)
2N=k(2x+k+1)(2)
That means, the problem is to figure out all possible pairs of k and 2x+k+1 which are both divisors of a number 2N. To find a number of ways to factor 2N is the so-called Integer Factorisation problem.
The best way to solve this problem is to run Shor's Algorithm on the quantum computer, that requires O(log2NloglogNlogloglogN) time. If there is no quantum computer in the interview room, just use classical GNFS Algorithm, which runs in a decent O(elog1/3N(loglogN)2/3) time.
Speaking seriously, one has to stay reasonable during the interview and figure out the right balance between speed and simplicity.
Time Complexity to Target During the Interview: O(N)
First, one could iterate from 1 to N and figure out all divisors in a linear time.
Second, the divisors are paired, i.e. if number i is a divisor of N, then number N/i is a divisor of N too. That means it's enough to iterate up to N.
O(N) is definitely enough for the interview.
In this article, we consider two simple solutions,
which are good suite for the interview and keep the rest out of scope.
Approach 1: Mathematical: Sum of First k Natural Numbers, O(N) time
Intuition
Let's use the formula we derived above
N=xk+2k(k+1)(1)
derive x
x=kN−2k+1(3)
and set two constraints:
-
x should be greater or equal to zero.
-
x should be an integer.
The first constraint is easy to apply using completing the square technique
kN≥2k+1(4)
2N+41≥(k+21)2(5)
k≤2N+41−21(6)
The first constraint sets the upper boundary for k. The second constraint, x should be an integer, can be verified during the iteration over k.
Algorithm
-
Initiate the counter to zero.
-
Iterate over k from 1 to 2N+41−21.
-
If x=kN−2k+1 is an integer, increase the counter by one.
-
Return the counter.
Implementation
Complexity Analysis
-
Time Complexity: O(N).
-
Space Complexity: O(1).
Approach 2: Mathematical: Decrease N Gradually, O(N) time
Intuition
Now let's optimize Approach 1. The idea is to use the same iteration limits for k, and to decrease N by k at each step.
At each step, we check if N can be composed by the sum of k consecutive numbers, i.e. N=(x+1)+(x+2)+...+(x+k)=xk+(1+2+...+k).
By removing all the complementary terms (1, 2, ... k) one by one,
we reduce the number N from
xk+(1+2+...+k) down to N=xk.
Since x should be an integer, k should be a divisor of N,
i.e. N % k == 0.
Algorithm
-
Initiate the counter to zero.
-
Iterate over k from 1 to 2N+41−21.
-
Decrease N by k, to keep xk term only.
-
Verify that x is an integer: N % k == 0. If it's the case, increase the counter by one.
-
Return the counter.
Implementation
Complexity Analysis
-
Time Complexity: O(N).
-
Space Complexity: O(1).
June 16, 2020 9:08 AM
If there is no quantum computer in the interview room....
December 22, 2020 9:30 AM
If somebody asks you this in the interview, don't take that offer and also let people know on blind/reddit/leetcode forums etc so other people can also save their time from such stupid companies.
how many mathematicians does it take to write a web server? )
August 3, 2020 1:55 AM
The discussion section has way better answers than this. For anyone who came down to check the comments....don't bother with the solution.
August 17, 2020 6:18 AM
A bit pedantic, "well-known formula for the sum of natural numbers." Solutions here all rely on the assumption that we know or can derive this.
Also 1+2+3+4+5+6 != 15 as stated
January 3, 2021 7:07 AM
This is a very ProjectEuler type of question.
Here's my simple understanding of the problem:
For representing N as sum of consecutive integers we have the following scenarios:
N = M + 0 (Base case when M == N, or when N is sum of only one number i.e itself)
N = M + (M + 1) (when N is sum of two consecutive numbers e.g 9 = 4+5, here M is 4 ) => 2M + 1
N = M + (M+1) + (M+2) (when N is sum of 3 consecutive numbers, e.g 9 = 2+3+4, here M is 2) => 3M + 3
N = M + (M+1) + (M+2) + (M+3) => 4*M + 6
N = M + (M+1) + (M+2) + (M+3) + (M+4) => 5M + 10
N = M + (M+1) + (M+2) + (M+3) + (M+4) + (M + 5) => 6M + 15
....... and so on
so looking at this series we need to find the unique numbers of M such that they fit our equations. (M needs to be an integer)
So we can write it as something like this =>
class Solution:
def consecutiveNumbersSum(self, N: int) -> int:
constant_term = 0
divisor = 1
ans = 0
while constant_term < N:
if ((N-constant_term)/divisor).is_integer():
ans += 1
constant_term = constant_term + divisor
divisor += 1
return ans
we are looping till constant_term is less than N, because
1.) if the constant term becomes greater than N there'll be no solution furthermore.
2.) if the constant term gets equal to N then this case will be similar to the very first case.
Found a solution that is to find the count of "odd factors". But don't ask me, I don't know why....
def consecutiveNumbersSum(self, N):
count = 0
for i in range(1, int(math.sqrt(N))+1):
if N%i == 0:
if i%2:
count += 1
if (N/i)%2 and N/i != i:
count += 1
return count
Simple Solution : check if((f1 + f2)%2 == 1 && abs(f1 - f2)%2==1) for all factor pairs f1, f2
- Tauqueer Ahmed, THE GREAT MATHEMATICIAN
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: int consecutiveNumbersSum(int n) { }};



